#!/usr/bin/env python3

"""
Minimum Path Sum:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which 
minimizes the sum of all numbers along its path.

Input: 
[ [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]  ]
Output: 7
Explanation: 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum
"""
class Solution:
    def min_path_sum(self, grid):
        y = len(grid)
        if y == 0:
            return 0
        x = len(grid[0])
        for y_index in range(y - 1, -1, -1):
            row = grid[y_index]
            for x_index in range(x - 1, -1, -1):
                current = row[x_index]
                if x_index == x - 1:
                    current_right = -1
                else:
                    current_right= row[x_index + 1]
                if y_index == y - 1:
                    current_down = -1
                else:
                    current_down = grid[y_index + 1][x_index]

                if current_right == -1 and current_down == -1:
                    continue
                elif current_right != -1 and current_down == -1:
                    row[x_index] += current_right
                elif current_down != -1 and current_right == -1:
                    row[x_index] += current_down
                else:
                    row[x_index] += min(current_right, current_down)
        return grid[0][0]


if __name__ == '__main__':
    s = Solution()
    input = [
        [1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]
    ]
    result = s.min_path_sum(input)
    print(str(result))
